COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00012 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\let\phi=\varphi
\magnification\magstephalf
\baselineskip 14 pt
\leftline{\sevenrm A89.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 18, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
A {\it relation from} $R$ {\it to} $S$ is a subset of $R \times S$, i.e.
a set of ordered pairs $\langle r,s\rangle$ with $r\in R$, $s\in S$.  Relations
will be named by lower case Greek letters.  A relation can be exhibited by
its {\it graph}: a figure with a point for each member of $R\cup S$, and an
arrow from $r$ to $s$ if $\langle r,s\rangle$ belongs to the relation.  If
$R$ and $S$ are finite, the relation can also be represented by its {\it matrix},
a table with rows indexed by $R$ and columns indexed
by $S$ containing 1 ($=$ TRUE) or 0 ($=$ FALSE) at the intersection of row
$r$ and column $s$ according to whether $\langle r,s\rangle$ belongs to
the relation or not.

[Examples go here]

If a relation is from $R$ to $S$, we call $R$ the {\it domain} and $S$ the
{\it codomain}.  If a relation is from $R$ to $R$, we call it a relation
{\it on} $R$.

Because a relation is a set, we may use the notations of set theory, such as
$\emptyset\subset\mu\subset\nu\subset R\times S$.  To say that $\langle r,s\rangle
\in\rho$, we usually use the abbreviated form $r\rho s$.

If $\mu$ is a relation from $R$ to $S$ and $\nu$ a relation from $S$ to $T$,
their {\it composition} $\mu\circ\nu$ is the relation from $R$ to $T$ that
contains $\langle x,z\rangle$ if there is some $y\in S$ for which $x\mu y$
and $y\nu z$.  Composition is associative: $(\mu\circ\nu )\circ\pi = \mu\circ
(\nu\circ\pi )$.  The matrix of $\mu\circ\nu$ is the boolean product of the
matrices of $\mu$ and $\nu$.

The {\it identity} relation $\delta↓R$ on $R$ is the set of ordered pairs
$\langle x,x\rangle$, $x\in R$.  If $\mu$ is a relation from $R$ to $S$,
$\delta↓R\circ\mu = \mu = \mu\circ\delta↓s$.

The {\it image} $X\circ\mu$ of $X$ under $\mu$ is the set of $y$ for which
some $\langle x,y\rangle \in\mu$ with $x\in X$.  The {\it coimage} $\mu\circ Y$
is the set of $x$ for which some $\langle x,y\rangle\in\mu$ with $y\in Y$.
The {\it junction} $X\circ Y$ of two sets is the truth value of $X\cap Y
\not=\emptyset$.  This overloading of notation is justified because 
$(X\circ\mu)\circ Y = X\circ (\mu\circ Y)$, $(X\circ\mu)\circ\nu = X\circ
(\mu\circ\nu )$, and $(\mu\circ\nu )\circ Y =\mu\circ (\nu\circ Y)$.  We
therefore can omit parentheses, writing $X\circ\mu\circ\nu\circ Z$ to mean
the assertion that there are elements $x$, $y$, $z$, for which $x\in X$,
$x\mu y$, $y\nu z$, $z\in Z$.

We identify the set element $x$ with the corresponding singleton set
$\{x\}$.  Then $x\circ\mu\circ\nu\circ Z$ if there is some $y$ and some
$z\in Z$ for which $x\mu y$ and $y\nu z$.

A {\it total function} from $R$ to $S$ is a set of ordered pairs
$\langle x,y\rangle\in R\times S$ with each $x\in R$ occurring once as
first component.  Then a total function is a restricted kind of relation.
If $\rho$ is a total function, the usual functional notation $\rho(x)$ can
be written in relational notation as $x\circ\rho$.

A relation from $R$ to $S$ is a total function if each $x\in R$ occurs as a 
first component at most once and at least once.  We separate these two conditions.
If each $x\in R$ occurs at most once, the relation is {\it functional}.  If each
$x\in R$ occurs at least once, the relation is {\it total}.  A relation that is
total and functional is a total function.

If $\mu$ is a relation from $R$ to $S$, the {\it converse} $\mu↑{-1}$ of $\mu$ 
is the relation from $S$ to $R$, with $y\mu↑{-1} x \equiv x\mu y$.  Then
$X\circ\mu = \mu↑{-1}\circ X$, $(\mu\circ\nu )↑{-1} = \nu↑{-1}\circ\mu↑{-1}$,
$X\circ\mu\circ Y = Y\circ\mu↑{-1}\circ X$.

A relation $\mu$ from $S$ to $T$ is {\it surjective} (onto) if $S\circ\mu = T$,
and {\it injective} (1-to-1) if $s↓1\mu t$ and $s↓2\mu t$ implies $s↓1 = s↓2$.  
Then $\mu$ is  surjective iff $\mu↑{-1}$ is total, and $\mu$ is injective
iff $\mu↑{-1}$ is functional.  A relation is functional iff all the row sums of
its matrix are at most one, total if all the row sums are at least one, injective
if the column sums are at most one, and surjective if the column sums are at 
least one.

Suppose $\mu \subset R\times S$.  Show that $\mu\circ\mu↑{-1} = \delta↓R$ 
iff $\mu$ is total and injective.
Show that $\mu↑{-1}\circ\mu = \delta↓s$ iff $\mu$ is functional and surjective.
For both to be true, $\mu$ must be a total function that is injective and
surjective, a {\it bijection}.  A bijection on $R$ is called a {\it permutation}
of $R$.  For finite $R$, a total function on $R$ is injective if and only
if it is surjective.

Let $\mu$ be a partial function, and $x$ not be in its domain.  In the
conventional functional notation, $\mu (x)$ is undefined, but in the
relational calculus $x\mu = \{x\}\circ\mu$ is well defined as the empty set.

{\narrower\smallskip\noindent
{\bf Exercise:}  If $\mu$ is a relation on $R$, we can define $\mu↑n$ 
by $\mu↑0 = \delta$, $\mu↑{i+1} = \mu↑i\circ\mu$.  Show that for
non-negative exponents, $\mu↑a\circ\mu↑b = \mu↑{a+b}$.  Show that $(\mu↑{-1})↑n
= (\mu↑n)↑{-1}$.  Defining $\mu↑{-n}$ as either of the above, show 
$\mu↑{-a}\circ\mu↑{-b} = \mu↑{-(a+b)}$.  Show if
$ab > 0$, $\mu↑a\circ\mu↑b = \mu↑{a+b}$ is not always true.
\smallskip
{\bf Execrcise:}  If $\mu\circ\mu↑{-1} = \nu$, what can be inferred about
$\nu$?
\smallskip
{\bf Exercise:}  If $\mu\circ\mu↑{-1}\subset\delta$, what can be inferred about
$\mu$?  If $\delta\circ\mu\circ\mu↑{-1}$, what can be inferred 
about $\mu$?\smallskip}
\bye